"""
https://leetcode.cn/problems/palindrome-linked-list/description/

234. 回文链表
已解答
简单
相关标签
premium lock icon
相关企业
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

 

示例 1：


输入：head = [1,2,2,1]
输出：true
示例 2：


输入：head = [1,2]
输出：false
 

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
 

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？



"""

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from typing import Optional
from list_node import ListNode,create_list_node,calc_arr


class Solution:
    """
    限制条件中，有一个比较特殊的点：node.val范围在0~9之间。

    如果不考虑时间复杂度和空间复杂度，比较容易解决。

    1   2   2   1
    1   2
    2   2

    必要条件可用：分别统计各个数字用到了多少，且能据此得到回文数前半段各用了多少数字。
    也可获得，如果是回文数，则其中点的位置。
    可考虑获取中点后，将中点后的所有节点next翻转，进而拿到最后一个节点。

    """
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        if not head:
            return True
        if not head.next:
            return True

        siz=1
        temp=head
        while temp.next:
            siz+=1
            temp=temp.next
        
        # 从数学上讲：如果是偶数，则从siz/2+1开始数；如果是奇数，则从(siz+1)/2开始数
        # 从代码上将，如果是偶数，则从siz/2开始数后半段；如果是奇数，则从(siz+1)//2开始数后半段
        back_start=(siz+1)//2
        idx=0
        temp=head
        while idx<back_start:
            idx+=1
            temp=temp.next
        
        # 翻转
        # back_node=temp
        fore=temp
        mid=temp.next
        while mid:
            back=mid.next
            mid.next=fore
            fore=mid
            mid=back
        end_node=fore

        # 遍历
        left_temp=head
        right_temp=end_node
        for i in range(siz//2):
            # print(f'{left_temp.val}?={right_temp.val}')
            if left_temp.val==right_temp.val:
                left_temp=left_temp.next
                right_temp=right_temp.next
            else:
                return False
            
        return True
    
if __name__=='__main__':
    nums=[1,2,3,2,1]
    head=create_list_node(nums)

    sol=Solution()
    res=sol.isPalindrome(head)
    print(res)
    pass